package me.eg.eight;

import java.util.HashSet;
import java.util.Set;

/**
 * 200. 岛屿数量
 * <p>
 * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 * <p>
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 * <p>
 * 此外，你可以假设该网格的四条边均被水包围。
 * <p>
 * 链接：https://leetcode-cn.com/problems/number-of-islands
 */
public class NumIslands {
    /**
     * 解法：并查集
     * 时间复杂度：O(M * N * α(M * N))
     * 空间复杂度：O(M * N)
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] fa = new int[m * n + 1];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '0') continue;

                int pos = getIndex(i, j, n);
                fa[pos] = pos;
                // 向左
                if (j > 0 && grid[i][j - 1] == '1') {
                    fa[find(fa[pos], fa)] = find(getIndex(i, j - 1, n), fa);
                }
                // 向上
                if (i > 0 && grid[i - 1][j] == '1') {
                    fa[find(fa[pos], fa)] = find(getIndex(i - 1, j, n), fa);
                }
            }
        }

        Set<Integer> islands = new HashSet<>();
        for (int i = 1; i <= m * n; i++) {
            if(fa[i] == 0) continue;
            islands.add(find(fa[i], fa));
        }
        return islands.size();
    }

    private int find(int x, int[] fa) {
        if (x == fa[x]) return x;
        return fa[x] = find(fa[x], fa);
    }

    private int getIndex(int x, int y, int cols) {
        return x * cols + y + 1;
    }
}
